package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printInorder

/**
https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

# 108. 将有序数组转换为二叉搜索树

## 示例 1：

输入：nums = [-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]

##示例 2：

输入：nums = [1,3]

输出：[3,1]
 */
class leetcode_108 {
    @Test
    fun test_1() {
        val n0 = TreeNode(0)
        val n_3 = TreeNode(-3)
        val n_10 = TreeNode(-10)
        val n9 = TreeNode(9)
        val n5 = TreeNode(5)
        val root = n0
        n0.left = n_3
        n0.right = n9
        n_3.left = n_10
        n9.left = n5
        val actual = sortedArrayToBST(intArrayOf(-10, -3, 0, 5, 9))
        val expect = root
        Assert.assertEquals(printInorder(expect).toString(), printInorder(actual).toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        val root = n3
        root.left = n1
        val actual = sortedArrayToBST(intArrayOf(1, 3))
        val expect = root
        Assert.assertEquals(printInorder(expect).toString(), printInorder(actual).toString())
    }

    fun sortedArrayToBST(nums: IntArray): TreeNode? {
        /**
         * 题型：
         * 二叉搜索树，二分法
        注意：
        1 平衡二叉搜索树
        2 思路：寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
        3 区间：[left, right]

        时间复杂度：O(logn)，其中 n 是数组的长度。
        空间复杂度：O(n)，其中 n 是数组的长度.
         */
        return build(nums, 0, nums.size - 1)
    }

    fun build(nums: IntArray, left: Int, right: Int): TreeNode? { // [left, right]
        // 1 终止条件 left > right
        if (nums.size == 0) {
            return null
        }

        if (nums.size == 1) {
            val node: TreeNode = TreeNode(nums[0])
            return node
        }

        if (left > right) {
            return null
        }

        // 2 中间节点 index： left + （right - left） / 2
        // 最中间的值作为node
        val mid: Int = left + ((right - left) / 2)
        val node: TreeNode = TreeNode(nums[mid])

        // 3 切割左数组
//        val left1: Int = left
//        val right1:Int = mid-1
//
//        // 4 切割右数组
//        val left2 : Int = mid + 1
//        val right2 : Int = right
//
//        // 5 递归
//        node.left = sortedArrayToBST(nums, left1, right1)
//        node.right = sortedArrayToBST(nums, left2, right2)
//        return node

        // 构造左孩子
        node.left = build(nums, left, mid - 1) // [left, mid - 1]
        // 构造右孩子
        node.right = build(nums, mid + 1, right) // [mid + 1, right]
        return node
    }
}